package leetcode.editor.cn;
//序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方
//式重构得到原数据。 
//
// 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串
//反序列化为原始的树结构。 
//
// 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的
//方法解决这个问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,2,3,null,null,4,5]
//输出：[1,2,3,null,null,4,5]
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1]
//输出：[1]
// 
//
// 示例 4： 
//
// 
//输入：root = [1,2]
//输出：[1,2]
// 
//
// 
//
// 提示： 
//
// 
// 树中结点数在范围 [0, 104] 内 
// -1000 <= Node.val <= 1000 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 设计 字符串 二叉树 
// 👍 1087 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Codec {

    // 代表分隔符的字符
    String SEP = ",";
    // 代表 null 空指针的字符
    String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        // 用于拼接字符串
        StringBuilder sb = new StringBuilder();
        preorder(sb, root);
        return sb.toString();
    }

    private void preorder(StringBuilder sb, TreeNode root) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        preorder(sb, root.left);
        preorder(sb, root.right);
    }

    private void inorder(StringBuilder sb, TreeNode root) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        inorder(sb, root.left);
        sb.append(root.val).append(SEP);
        inorder(sb, root.right);
    }

    private void postorder(StringBuilder sb, TreeNode root) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        postorder(sb, root.left);
        postorder(sb, root.right);
        sb.append(root.val).append(SEP);
    }

    private void levelorder(StringBuilder sb, TreeNode root) {
        // 初始化队列，将 root 加入队列
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            /* 层级遍历代码位置 */
            if (cur == null) {
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(cur.val).append(SEP);
            q.offer(cur.left);
            q.offer(cur.right);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        // 将字符串转化成列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return predeserialize(nodes);
    }

    /* 辅助函数，通过 nodes 列表构造二叉树 */
    private TreeNode predeserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) return null;

        /******前序遍历位置******/
        // 列表最左侧就是根节点
        String first = nodes.removeFirst();
        if (first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        /***********************/

        root.left = predeserialize(nodes);
        root.right = predeserialize(nodes);

        return root;
    }

    /**
     * 无法实现
     *
     * @param nodes
     * @return
     */
    private TreeNode indeserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) return null;

        return null;
    }

    /* 辅助函数，通过 nodes 列表构造二叉树 */
    private TreeNode postdeserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) return null;

        /******后序遍历位置******/
        // 列表最右侧就是根节点
        String last = nodes.removeLast();
        if (last.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(last));
        /***********************/

        root.right = postdeserialize(nodes);
        root.left = postdeserialize(nodes);

        return root;
    }

    private TreeNode leveldeserialize(String data) {
        if (data.isEmpty()) return null;
        String[] nodes = data.split(SEP);
        // 第一个元素就是 root 的值
        if (nodes[0].equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));

        // 队列 q 记录父节点，将 root 加入队列
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        for (int i = 1; i < nodes.length; ) {
            // 队列中存的都是父节点
            TreeNode parent = q.poll();
            // 父节点对应的左侧子节点的值
            String left = nodes[i++];
            if (!left.equals(NULL)) {
                parent.left = new TreeNode(Integer.parseInt(left));
                q.offer(parent.left);
            } else {
                parent.left = null;
            }
            // 父节点对应的右侧子节点的值
            String right = nodes[i++];
            if (!right.equals(NULL)) {
                parent.right = new TreeNode(Integer.parseInt(right));
                q.offer(parent.right);
            } else {
                parent.right = null;
            }
        }
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
//leetcode submit region end(Prohibit modification and deletion)
